package Leetcode.网格图;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

/**
 * @Author: kirito
 * @Date: 2024/5/7 16:22
 * @Description:
 * 地图分析
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
 *
 * 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
 *
 * 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
 * 输出：2
 * 解释：
 * 海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
 * 示例 2：
 *
 *
 *
 * 输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
 * 输出：4
 * 解释：
 * 海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。
 *
 *
 * 提示：
 *
 * n == grid.length
 * n == grid[i].length
 * 1 <= n <= 100
 * grid[i][j] 不是 0 就是 1
 */

public class maxDistance {
    /**
     * 相信对于Tree的BFS大家都已经轻车熟路了：要把root节点先入队，然后再一层一层的无脑遍历就行了。
     *
     * 对于图的BFS也是一样滴～ 与Tree的BFS区别如下：
     * 1、tree只有1个root，而图可以有多个源点，所以首先需要把多个源点都入队。
     * 2、tree是有向的因此不需要标志是否访问过，而对于无向图来说，必须得标志是否访问过！
     * 并且为了防止某个节点多次入队，需要在入队之前就将其设置成已访问！
     *
     * 这是一道典型的BFS基础应用，为什么这么说呢？
     * 因为我们只要先把所有的陆地都入队，然后从各个陆地同时开始一层一层的向海洋扩散，那么最后扩散到的海洋就是最远的海洋！
     * 并且这个海洋肯定是被离他最近的陆地给扩散到的！
     * 下面是扩散的图示，1表示陆地，0表示海洋。每次扩散的时候会标记相邻的4个位置的海洋：
     *
     * 作者：Sweetiee 🍬
     * 链接：https://leetcode.cn/problems/as-far-from-land-as-possible/solutions/176105/jian-dan-java-miao-dong-tu-de-bfs-by-sweetiee/
     * @param grid
     * @return
     */
    // 定义一个函数，用于计算网格中点到源点的最大距离
    public int maxDistance(int[][] grid) {
        // 获取网格的行数，也是列数，因为假设网格是正方形的
        int n = grid.length;
        // 初始化一个双端队列，用于存储从源点出发的单元格
        Deque<int[]> d = new ArrayDeque<>();
        // 遍历网格的所有单元格
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 如果单元格的值是1，表示它是可达的，将其加入队列，并将值设置为-1，以表示已访问
                if (grid[i][j] == 1) {
                    d.addLast(new int[]{i, j});
                    grid[i][j] = -1;
                }
            }
        }
        // 初始化答案为-1，表示如果没有可达点，则返回-1
        int ans = -1;
        // 定义一个方向数组，表示可以移动的方向
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        // 当队列不为空时，继续执行
        while (!d.isEmpty()) {
            // 从队列的头部取出一个单元格
            int[] poll = d.pollFirst();
            int dx = poll[0], dy = poll[1];
            // 获取当前单元格到源点的距离，如果没有则取0
            int step = Math.max(grid[dx][dy], 0);
            // 遍历所有可能移动的方向
            for (int[] di : dirs) {
                int nx = dx + di[0], ny = dy + di[1];
                // 如果新的位置在网格范围内
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                    continue;
                }
                // 如果新的位置的值不为0，说明它已经被访问过或者不可达
                if (grid[nx][ny] != 0) {
                    continue;
                }
                // 将新的位置加入队列，并更新其值为当前步数加1
                d.addLast(new int[]{nx, ny});
                grid[nx][ny] = step + 1;
                // 更新答案为当前步数加1和之前答案的最大值
                ans = Math.max(ans, step + 1);
            }
        }
        // 返回最大距离
        return ans;
    }

    public int maxDistance2(int[][] grid) {
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        Queue<int[]> queue = new ArrayDeque<>();
        int m = grid.length, n = grid[0].length;
        // 先把所有的陆地都入队。
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[] {i, j});
                }
            }
        }

        // 从各个陆地开始，一圈一圈的遍历海洋，最后遍历到的海洋就是离陆地最远的海洋。
        boolean hasOcean = false;
        int[] point = null;
        while (!queue.isEmpty()) {
            point = queue.poll();
            int x = point[0], y = point[1];
            // 取出队列的元素，将其四周的海洋入队。
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] != 0) {
                    continue;
                }
                grid[newX][newY] = grid[x][y] + 1; // 这里我直接修改了原数组，因此就不需要额外的数组来标志是否访问
                hasOcean = true;
                queue.offer(new int[] {newX, newY});
            }
        }

        // 没有陆地或者没有海洋，返回-1。
        if (point == null || !hasOcean) {
            return -1;
        }

        // 返回最后一次遍历到的海洋的距离。
        return grid[point[0]][point[1]] - 1;

    }


}
